import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * Created by zhourh on 2018/9/10.
 *
 * 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

 案例 1:

 输入:
 5
 / \
 3   6
 / \   \
 2   4   7

 Target = 9

 输出: True


 案例 2:

 输入:
 5
 / \
 3   6
 / \   \
 2   4   7

 Target = 28

 输出: False

 */
public class TwoSumIV {

    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(5);
        TreeNode node3 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        node5.left = node3;
        node5.right = node6;
        node3.left = node2;
        node3.right = node4;
        node6.right = node7;

        System.out.println(new TwoSumIV().findTarget(node5, 9));
        System.out.println(new TwoSumIV().findTarget(node5, 28));
    }

    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }

        Set<Integer> numbers = new HashSet<Integer>();
        travel(root, numbers);

        Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            int value = iterator.next();
            if (value * 2 != k && numbers.contains(k - value)) {
                return true;
            }
        }

        return false;

    }

    private void travel(TreeNode node, Set<Integer> numbers) {
        if (node.left != null) {
            travel(node.left, numbers);
        }

        numbers.add(node.val);

        if (node.right != null) {
            travel(node.right, numbers);
        }
    }
}
